package com.bupt.chapter.first.different_pies;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
	public static void main(String[] args) {
		Solution s = new Solution();
		// s.swap(new int[] { 3, 1, 4, 2, 5, 6 }, 2);
		// s.sort(new int[] { 3, 2, 1, 6, 5, 4, 9, 8, 7, 0 });
		s.find(new int[] { 3, 2, 1, 6, 5, 4, 9, 8, 7, 0 });
	}

	public int sort(int[] nums) {
		int[] temp = new int[nums.length];
		for (int i = 0; i < temp.length; i++) {
			temp[i] = nums[i];
		}
		int i = temp.length;
		int times = 0;
		while (i > 0) {
			int max = 0;
			for (int j = 0; j < i; j++) {
				if (temp[max] < temp[j])
					max = j;
			}
			if (max != --i) {

				swap(temp, max);
				swap(temp, i);
				times++;
				times++;
			}
		}
		// System.out.println(times);
		return times;
	}

	int max, min;
	int times;
	List<List<Integer>> list;
	List<List<Integer>> result;

	public void find(int[] nums) {
		max = min = sort(nums);
		times = 0;
		list = new ArrayList<List<Integer>>();
		find(nums, 0, 0);
		System.out.println("max:" + max + " min:" + min + " time:" + times);
		System.out.println(result);
	}

	public void find(int[] nums, int count, int swap) {
		if (count < min) {
			times++;
			if (isSorted(nums)) {
				min = count;
				result = new ArrayList<List<Integer>>(list);
			} else {
				for (int i = 0; i < nums.length; i++) {
					if (i != swap) {
						swap(nums, i);
						list.add(getList(nums));
						find(nums, count + 1, swap);
						list.remove(list.size() - 1);
						swap(nums, i);
					}
				}
			}
		}
	}

	private List<Integer> getList(int[] nums) {
		List<Integer> temp = new ArrayList<Integer>();
		for (int j = 0; j < nums.length; j++) {
			temp.add(nums[j]);
		}
		return temp;
	}

	public boolean isSorted(int[] nums) {
		for (int i = 0; i < nums.length - 1; i++) {
			if (nums[i] > nums[i + 1])
				return false;
		}
		return true;
	}

	public void swap(int[] nums, int end) {
		if (end <= 0)
			return;
		if (end >= nums.length)
			return;
		for (int i = 0; i < end / 2 + 1; i++) {
			int temp = nums[i];
			nums[i] = nums[end - i];
			nums[end - i] = temp;
		}
		// System.out.println(Arrays.toString(nums));
	}
}
